Générer une Matrice de Contiguïté pour un Graphe Pondéré

Donc, vous semblez ne pas être familiarisés avec Graphiques, jetez un oeil à Wikipedia. Aussi parcourir pour certaines images, il devient plus facile à comprendre.

Peu de concept

Votre image peut être représentée comme une Graph. Généralement, les graphiques sont mis en œuvre à l'aide de 2 types d'éléments, Nodes et Links (parfois appelé Arcs).

Un Node représenter les lettres à votre image, ils seraient A, B, C, etc.
Un Arc ou Link, est la ligne qui connecte deux nœuds, si vous regardez la connexion entre H à L, avoir un lien entre les deux, dans un graphe pondéré, de liens différents, ont des poids différents.

La résolution de votre problème - Partie 1

Ce que nous avons à faire est de représenter votre image sous forme de graphique dans le code, donc, nous allons commencer à créer les éléments de base Node et Arc:

Nœud

Un nœud a un Name, afin que nous puissions identifier le nœud. Et un nœud peut être connecté à d'autres nœuds, nous pourrions utiliser une collection de Noeuds, mais le vôtre est un graphe pondéré, donc, chacune des connexions doit être représentée par le nœud lié et c'est le poids. Par conséquent, nous utilisons une collection d'Arcs.

public class Node
{
    public string Name;
    public List<Arc> Arcs = new List<Arc>();

    public Node(string name)
    {
        Name = name;
    }

    ///<summary>
    ///Create a new arc, connecting this Node to the Nod passed in the parameter
    ///Also, it creates the inversed node in the passed node
    ///</summary>
    public Node AddArc(Node child, int w)
    {
        Arcs.Add(new Arc
        {
            Parent = this,
            Child = child,
            Weigth = w
        });

        if (!child.Arcs.Exists(a => a.Parent == child && a.Child == this))
        {
            child.AddArc(this, w);
        }

        return this;
    }
}

Arc

Vraiment simple de la classe, il contient les nœuds liés, et le poids de la connexion:

public class Arc
{
    public int Weigth;
    public Node Parent;
    public Node Child;
}

Graphique

Graphique est une sorte de classe wrapper, pour l'organisation fins. J'ai aussi déclaré une Racine pour le graphique, nous ne sommes pas à l'utiliser, mais il est utile dans plusieurs cas:

public class Graph
{
    public Node Root;
    public List<Node> AllNodes = new List<Node>();

    public Node CreateRoot(string name)
    {
        Root = CreateNode(name);
        return Root;
    }

    public Node CreateNode(string name)
    {
        var n = new Node(name);
        AllNodes.Add(n);
        return n;
    }

    public int?[,] CreateAdjMatrix()
    {
        //Matrix will be created here...
    }
}

La résolution de votre problème - Partie 2

Maintenant, nous avons tous la structure de données pour la tenue de la graphique, nous allons le remplir avec des données. Voici un code qui initialise un graphique similaire à votre cube image. C'est ennuyeux et terne, mais dans la vraie vie les cas, le graphique est créée dynamiquement:

static void Main(string[] args)
{
var graph = new Graph();
var a = graph.CreateRoot("A");
var b = graph.CreateNode("B");
var c = graph.CreateNode("C");
var d = graph.CreateNode("D");
var e = graph.CreateNode("E");
var f = graph.CreateNode("F");
var g = graph.CreateNode("G");
var h = graph.CreateNode("H");
var i = graph.CreateNode("I");
var j = graph.CreateNode("J");
var k = graph.CreateNode("K");
var l = graph.CreateNode("L");
var m = graph.CreateNode("M");
var n = graph.CreateNode("N");
var o = graph.CreateNode("O");
var p = graph.CreateNode("P");
a.AddArc(b, 1)
.AddArc(c, 1);
b.AddArc(e, 1)
.AddArc(d, 3);
c.AddArc(f, 1)
.AddArc(d, 3);
c.AddArc(f, 1)
.AddArc(d, 3);
d.AddArc(h, 8);
e.AddArc(g, 1)
.AddArc(h, 3);
f.AddArc(h, 3)
.AddArc(i, 1);
g.AddArc(j, 3)
.AddArc(l, 1);
h.AddArc(j, 8)
.AddArc(k, 8)
.AddArc(m, 3);
i.AddArc(k, 3)
.AddArc(n, 1);
j.AddArc(o, 3);
k.AddArc(p, 3);
l.AddArc(o, 1);
m.AddArc(o, 1)
.AddArc(p, 1);
n.AddArc(p, 1);
//o - Already added
//p - Already added
int?[,] adj = graph.CreateAdjMatrix(); //We're going to implement that down below
PrintMatrix(ref adj, graph.AllNodes.Count); //We're going to implement that down below
}

La résolution de votre problème - Partie 3

Donc, nous avons un completelly initialisé graphique, nous allons créer la matrice. La méthode suivante crée une matrice à deux dimensions, n par n, où n est le nombre de nœud de nous obtenir à partir du graphique de la classe. Foreach des nœuds, on recherche s'ils ont un lien, si elles ont un lien, un rempli la matrice dans la position appropriée. Regarder qui dans votre matrice de contiguïté exemple, vous n'avez 1s, ici j'ai mis le poids de la le lien, j'ai mis de cette façon, donc il n'y a aucun sens à avoir une pondéré graphique!

public int?[,] CreateAdjMatrix()
{
int?[,] adj = new int?[AllNodes.Count, AllNodes.Count];
for (int i = 0; i < AllNodes.Count; i++)
{
Node n1 = AllNodes[i];
for (int j = 0; j < AllNodes.Count; j++)
{
Node n2 = AllNodes[j];
var arc = n1.Arcs.FirstOrDefault(a => a.Child == n2);
if (arc != null)
{
adj[i, j] = arc.Weigth;
}
}
}
return adj;
}

Fait

Que cela est fait, vous avez votre pondérée de la matrice de contiguïté, d'une certaine façon à imprimer:

private static void PrintMatrix(ref int?[,] matrix, int Count)
{
Console.Write("       ");
for (int i = 0; i < Count; i++)
{
Console.Write("{0}  ", (char)('A' + i));
}
Console.WriteLine();
for (int i = 0; i < Count; i++)
{
Console.Write("{0} | [ ", (char)('A' + i));
for (int j = 0; j < Count; j++)
{
if (i == j)
{
Console.Write(" &,");
}
else if (matrix[i, j] == null)
{
Console.Write(" .,");
}
else
{
Console.Write(" {0},", matrix[i, j]);
}
}
Console.Write(" ]\r\n");
}
Console.Write("\r\n");
}

De quoi nous donner le résultat suivant:

       A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P
A | [  &, 1, 1, ., ., ., ., ., ., ., ., ., ., ., ., ., ]
B | [  1, &, ., 3, 1, ., ., ., ., ., ., ., ., ., ., ., ]
C | [  1, ., &, 3, ., 1, ., ., ., ., ., ., ., ., ., ., ]
D | [  ., 3, 3, &, ., ., ., 8, ., ., ., ., ., ., ., ., ]
E | [  ., 1, ., ., &, ., 1, 3, ., ., ., ., ., ., ., ., ]
F | [  ., ., 1, ., ., &, ., 3, 1, ., ., ., ., ., ., ., ]
G | [  ., ., ., ., 1, ., &, ., ., 3, ., 1, ., ., ., ., ]
H | [  ., ., ., 8, 3, 3, ., &, ., 8, 8, ., 3, ., ., ., ]
I | [  ., ., ., ., ., 1, ., ., &, ., 3, ., ., 1, ., ., ]
J | [  ., ., ., ., ., ., 3, 8, ., &, ., ., ., ., 3, ., ]
K | [  ., ., ., ., ., ., ., 8, 3, ., &, ., ., ., ., 3, ]
L | [  ., ., ., ., ., ., 1, ., ., ., ., &, ., ., 1, ., ]
M | [  ., ., ., ., ., ., ., 3, ., ., ., ., &, ., 1, 1, ]
N | [  ., ., ., ., ., ., ., ., 1, ., ., ., ., &, ., 1, ]
O | [  ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ., ]
P | [  ., ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ]

OriginalL'auteur RMalke