Data

Tools

Indexes

Applications

Experiments

Open Source Science

cmpe492_partitioning_undirected_graphs

CMPE 492 project that proposes an integer programming solution to graph partitioning problem. Fall 2023 Boğaziçi University

https://github.com/araldortogul/cmpe492_partitioning_undirected_graphs

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 (5.4%) to scientific vocabulary
Last synced: 10 months ago · JSON representation ·

Repository

CMPE 492 project that proposes an integer programming solution to graph partitioning problem. Fall 2023 Boğaziçi University

Basic Info
  • Host: GitHub
  • Owner: araldortogul
  • Language: Python
  • Default Branch: main
  • Size: 3.66 MB
Statistics
  • Stars: 0
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 1
Created over 2 years ago · Last pushed over 2 years ago
Metadata Files
Readme Citation

README.md

CMPE 492 Project: Partitioning Undirected Graphs

Graduation project that aims to partition undirected graphs to 2 equal sized subgraphs by cutting minimum number of edges. Edges can have positive weights.

Example Output

30 vertices with weightless edges | 80 vertices with weightless edges :-------------------------:|:-------------------------: example partition 1 | example partition 2

20 vertices with weighted edges | 50 vertices with weidghted edges :-------------------------:|:-------------------------: example partition 3 | example partition 4

Running the Program

[!IMPORTANT] The program requires a Gurobi license to run. For more information about Gurobi's licenses, please check Gurobi's website.

The program can be run with the following command:

console ./graph_partitioner.py

Owner

  • Name: Aral Dörtoğul
  • Login: araldortogul
  • Kind: user
  • Location: Istanbul

I am a senior industrial and computer engineering student who enjoys connecting dots. Keen on software development, system dynamics & simulation, forecasting

Citation (CITATION.cff) 

# This CITATION.cff file was generated with cffinit.
# Visit https://bit.ly/cffinit to generate yours today!

cff-version: 1.2.0
title: Graph Partitioner
message: >-
  If you use this software, please cite it using the
  metadata from this file.
type: software
authors:
  - given-names: Aral
    family-names: Dörtoğul
    email: araldortogul@gmail.com
    affiliation: Boğaziçi University
repository-code: >-
  https://github.com/araldortogul/CMPE492_Partitioning_Undirected_Graphs
abstract: >-
  CMPE 492 project that proposes an integer programming
  solution to "graph partitioning problem".
keywords:
  - graph
  - partition
  - integer
  - programming
  - model
  - graph theory
  - operations research
  - min cut

GitHub Events

Total
Last Year

Dependencies

requirements.txt pypi
  • contourpy ==1.2.0
  • cycler ==0.12.1
  • fonttools ==4.47.2
  • gurobipy ==10.0.0
  • igraph ==0.11.3
  • kiwisolver ==1.4.5
  • matplotlib ==3.8.2
  • numpy ==1.26.3
  • packaging ==23.2
  • pillow ==10.2.0
  • pyparsing ==3.1.1
  • python-dateutil ==2.8.2
  • scipy ==1.11.4
  • six ==1.16.0
  • texttable ==1.7.0