Data

Tools

Indexes

Applications

Experiments

Open Source Science

graph-coloring

Wigderson's Approximate Graph Coloring Algorithm

https://github.com/azulqarni/graph-coloring

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (6.9%) to scientific vocabulary
Last synced: 6 months ago · JSON representation ·

Repository

Wigderson's Approximate Graph Coloring Algorithm

Basic Info
  • Host: GitHub
  • Owner: azulqarni
  • Language: C
  • Default Branch: main
  • Homepage:
  • Size: 200 KB
Statistics
  • Stars: 0
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Created almost 4 years ago · Last pushed almost 4 years ago
Metadata Files
Readme Citation

README.md

Wigderson’s Approximate Graph Coloring Algorithm

This is a Wigderson’s approximate graph coloring algorithm implementation along with a Python wrapper file for invocation of the algorithm's C implementation.

  • graphgen.c containts the code for the production of a random input graph with number of vertices specified by the first argument passed to the executable.
  • gcolor.c contains the algorithm imlementation in C accepting a graph that is stored in a adjacent list format. In each of the input graphs, vertices are numbered from 1 to |V|. Each row includes a vertex, followed by zero or more other vertices. For example:

    1 3 6
    2 3 5
    3 1 2 4 5
    4 3 5
    5 2 3 4 6
    6 1 5

    This input should be interpreted as follows: the undirected edges of G are (1,3), (1,6), (2,3), (2,5), (3,4), (3,5), (4,5) and (5,6). The vertices following the source vertex are in arbitrary order. The output consists of vertices grouped by color, with all vertices assigned with the same color printed in the same line of the output. In the first line, the number of colors used is printed. If gcolor.c is compiled with -DATTACHED an executable compatible with the python wrapper is produced, accepting the input graph as lines of adjacency lists, where vertices are enumerated with consecutive numbers starting from 0.
  • wrapper.py contains the Python wrapper script which provides the a function for the compatible program to be invoked on a graph that is stored in adjacency matrix format, featuring interprocess communication, which returns vertices grouped by color in one list of lists.
  • Run setup.sh to compile and test the above script and programs.

Performance Comparison for Random Graph with |V|=8000 (×7.64 Speedup)

Implementation @Intel(R) Xeon(R) CPU E3-1245 v5 @ 3.50GHz| Measured Time (s) | Colors Returned :----------------------------------------------------------|-------------------|----------------: Current Wigderson’s in Algorithm C | 6.976 | 726 NetworkX (strategy_largest_first) in Python | 53.277 | 719

Owner

  • Login: azulqarni
  • Kind: user

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
  - family-names: Zoulkarni
    given-names: Asim
title: "Wigderson’s Approximate Graph Coloring Algorithm"
url: https://github.com/azulqarni/graph-coloring
date-released: 2022-03-14

GitHub Events

Total
Last Year